1. Field of the Invention
This invention relates to an image processing method and device for transforming an image of a graphic stored in an image memory and displaying the transformed image on a display device, and a storage medium storing a program therefor.
2. Prior Art
In video game machines and the like, a screen view is formed by reading image data of graphics necessary for forming respective parts of one screen view from an image memory storing image data of various graphics, generating write addresses corresponding to positions of the read image data of each graphic within the one screen view, and writing the image data of graphics in areas of a frame buffer corresponding to the respective write addresses. During the screen view formation, it is generally employed to rotate or transform a graphic or graphics in the screen view by controlling read addresses of the image data of the graphic or graphics stored in the image memory, and write addresses of the same in the frame buffer. This kind of technique is generally called xe2x80x9ctwo-dimensional renderingxe2x80x9d. For the convenience of description, throughout the present specification, the term xe2x80x9ctransform (transformation)xe2x80x9d is used in a broader sense than usual, i.e. as a general term for image-tranforming operations including not only transformation as its normal meaning but also rotation or the like. In the appended claims as well, the term xe2x80x9ctransform (transformation)xe2x80x9d is used in the broader sense.
The two-dimensional rendering, referred to above, is generally implemented by steps of calculating transform functions for mapping positions of parts of a graphic subjected to transformation (post-transformation graphic) over corresponding positions of the same graphic before being subjected to transformation (pre-transformation graphic), converting, using the transform functions, the positions of the parts of the graphic subjected to transformation on a display screen view to corresponding positions of the pre-transformation graphic, and reading image data corresponding to the positions of the pre-transformation graphic from the image memory. However, the above transform functions for use in the two-dimensional rendering include multiplications and divisions. Therefore, a VDP (video decompression processor) designed for the two-dimensional rendering is required to perform high-speed multiplying/dividing operations, resulting in an increased manufacturing cost of the VDP.
It is an object of the present invention to provide an image processing method that is capable of generating an image containing graphics which are transformed without carrying out multiplying/dividing operations, an image processing device for implementing the image processing method, and a storage medium storing a program for executing the image processing method.
To attain the above object, according to a first aspect of the invention, there is provided an image processing method of generating image data of a transformed graphic from image data of a source graphic before transformation stored in an image memory, and storing the image data of the transformed graphic into a frame buffer.
The method according to the first aspect of the invention is characterized by comprising the steps of sequentially determining, by a first DDA algorithm-based process, horizontal coordinate values of a pair of first points of intersection where a horizontal scanline intersects with two of sides defining the transformed graphic, while advancing the horizontal scanline in a vertical direction by a unit amount; sequentially determining, by a second DDA algorithm-based process, horizontal coordinate values and vertical coordinate values of a pair of second points of intersection on sides of the source graphic corresponding respectively to the two of the sides defining the transformed graphic, the second points of intersection corresponding respectively to the first points of intersection; determining, by a third DDA algorithm-based process, a horizontal coordinate value and a vertical coordinate value of each of points on the source graphic corresponding to respective points on a horizontal line segment connecting between one and another of the first points and spaced from each other by the unit amount, the respective points being obtained by changing a horizontal coordinate from a horizontal coordinate value of the one of the first points to a horizontal coordinate value of the another of the first points by the unit amount, whenever the first DDA algorithm-based process and the second DDA algorithm-based process are executed; and reading out image data of a location specified by the horizontal coordinate value and the vertical coordinate value of the each of the points on the source graphic determined by the third DDA algorithm-based process, from the image memory, and writing the read out image data into the frame buffer as image data of each of the respective points on the horizontal line segment connecting between the one and the another of the first points on the transformed graphic and spaced from each other by the unit amount.
Preferably, the first DDA algorithm-based process to the third DDA algorithm-based process are based on a DDA algorithm based process for sequentially determining one of a pair of integer coordinate values corresponding to each of straight line-approximating ones of lattice points of a two-dimensional coordinate system as a second integer coordinate value in response to inputting of a first integer coordinate value corresponding to the one of the pair of integer coordinate values, the two-dimensional coordinate system having a first coordinate axis for specifying a first coordinate value and a second coordinate axis for specifying a second coordinate value, each of the lattice points being specified by an integer as the first coordinate value and an integer as the second coordinate value, the straight line-approximating ones approximating a straight line arranged in the two-dimensional coordinate system, wherein if a first numerical value corresponding to a length of the straight line along the first coordinate axis is larger than or not smaller than a second numerical value corresponding to a length of the straight line along the second coordinate axis, the first numerical value is accumulated whenever the first integer coordinate value is changed by a unit amount, and accumulation of the second numerical value and change of the second integer coordinate value by the unit amount are repeatedly carried out to update the second integer coordinate value each time such that the second integer coordinate value becomes farther from an initial value of the second integer coordinate value corresponding to one end of the straight line and becomes closer to a final value of the second integer coordinate value corresponding to another end of the straight line until the accumulated second numerical value exceeds the accumulated first numerical value, whereas if the first numerical value corresponding to the length of the straight line along the first coordinate axis is not larger than or smaller than the second numerical value corresponding to the length of the straight line along the second coordinate axis, the second numerical value is accumulated whenever the first integer coordinate value is changed by the unit amount, and accumulation of the first numerical value and change of the second integer coordinate value by the unit amount are repeatedly carried out to update the second integer coordinate value each time such that the second integer coordinate value becomes farther from the initial value of the second integer coordinate value corresponding to the one end of the straight line and becomes closer to the final value of the second integer coordinate value corresponding to the another end of the straight line until the accumulated first numerical value exceeds the accumulated second numerical value.
To attain the above object, according to a second aspect of the invention, there is provided an image processing method of generating image data of a transformed graphic from image data of a source graphic before transformation from an image memory, and storing the image data of the transformed graphic into a frame buffer.
The method according to the second aspect of the invention is characterized by executing a DDA algorithm-based process for sequentially determining one of a pair of integer coordinate values corresponding to each of straight line-approximating ones of lattice points of a two-dimensional coordinate system as a second integer coordinate value in response to inputting of a first integer coordinate value corresponding to the one of the pair of integer coordinate values, the two-dimensional coordinate system having a first coordinate axis for specifying a first coordinate value and a second coordinate axis for specifying a second coordinate value, each of the lattice points being specified by an integer as the first coordinate value and an integer as second, coordinate value, the straight line-approximating ones approximating a straight line arranged in the two-dimensional coordinate system, wherein if a first numerical value corresponding to a length of the straight line along the first coordinate axis is larger than or not smaller than a second numerical value corresponding to a length of the straight line along the second coordinate axis, the first numerical value is accumulated whenever the first integer coordinate value is changed by a unit amount, and accumulation of the second numerical value and a change of the second integer coordinate value by the unit amount are repeatedly carried out to update the second integer coordinate value each time such that the second integer coordinate value becomes farther from an initial value of the second integer coordinate value corresponding to one end of the straight line and becomes closer to a final value of the second integer coordinate value corresponding to another end of the straight line until the accumulated second numerical value exceeds the accumulated first numerical value, whereas if the first numerical value corresponding to the length of the straight line along the first coordinate axis is not larger than or smaller than the second numerical value corresponding to the length of the straight line along the second coordinate axis, the second numerical value is accumulated whenever the first integer coordinate value is changed by the unit amount, and accumulation of the first numerical value and change of the second integer coordinate value by the unit amount are repeatedly carried out to update the second integer coordinate value each time such that the second integer coordinate value becomes farther from the initial value of the second integer coordinate value corresponding to the one end of the straight line and becomes closer to the final value of the second integer coordinate value corresponding to the another end of the straight line until the accumulated first numerical value exceeds the accumulated second numerical value; and by comprising the steps of executing a transformed graphic intersection coordinate value-calculating process for sequentially carrying out the DDA algorithm-based process on each of two of sides defining the transformed graphic, with which a horizontal scanline intersects when it is moved vertically, with one of two ends of the each of the two of the sides which is first reached by the horizontal scanline set to a first starting point, another of the two ends set to a first ending point, a horizontal coordinate value of the first starting point set to the initial value of the second integer coordinate value used in the DDA algorithm-based process, a horizontal coordinate value of the first ending point set to the final value of the second integer coordinate value corresponding to the another end of the straight line used in the DDA algorithm-based process, and a vertical coordinate value defining the horizontal scanline set to the first integer coordinate value used in the DDA algorithm-based process, to thereby obtain the second integer coordinate value as a horizontal coordinate value of a corresponding one of a pair of first points of intersection where the horizontal scanline intersects with the two sides; executing a first source graphic intersection coordinate value-calculating process for sequentially carrying out the DDA algorithm-based process on one of sides defining the source graphic corresponding to the each of the two of the sides defining the transformed graphic, with a horizontal coordinate value of one end of the one of the sides defining the source graphic corresponding to the first starting point set to the initial value of the second integer coordinate value used in the DDA algorithm-based process, a horizontal coordinate value of another end of the one of the sides defining the source graphic corresponding to the first ending point set to the final value of the second integer coordinate value used in the DDA algorithm-based process, and the vertical coordinate value defining the horizontal scanline set to the first integer coordinate, to thereby obtain the second integer coordinate value as a horizontal coordinate value of a corresponding one of a pair of second points of intersection on the source graphic corresponding respectively to the pair of first points of intersection; executing a second source graphic intersection coordinate value-calculating process for sequentially carrying out the DDA algorithm-based process on the one of the sides defining the source graphic, with a vertical coordinate value of the one end of the one of the sides defining the source graphic corresponding to the first starting point set to the initial value of the second integer coordinate value used in the DDA algorithm-based process, a vertical coordinate value of the another end of the one of the sides defining the source graphic corresponding to the first ending point set to the final value of the second integer coordinate value used in the DDA algorithm-based process, and the vertical coordinate value defining the horizontal scanline set to the first integer coordinate value, to thereby obtain the second integer coordinate value as a vertical coordinate value of the corresponding one of the pair of second points of intersection on the source graphic corresponding respectively to the pair of first points of intersection; executing a horizontal coordinate value-calculating process for repeatedly carrying out the DDA algorithm-based process whenever the transformed graphic coordinate value-calculating process, the first source graphic coordinate value-calculating process, and the second source graphic coordinate value-calculating process are carried out one time, with a horizontal coordinate value of one of the pair of second points of intersection corresponding to one of the two sides defining the transformed graphic set to the initial value of the second integer coordinate value used in the DDA algorithm-based process, a horizontal coordinate value of another of the pair of second points of intersection corresponding to another of the two sides defining the transformed graphic set to the final value of the second integer coordinate value, and each of integer horizontal coordinate values on a horizontal line segment connecting between the pair of first points of intersection on the two sides defining the transformed graphic set to the first integer coordinate value used in the DDA algorithm-based process, to thereby obtain the second integer coordinate value as a horizontal coordinate value of each of points on the source graphic corresponding to respective points on the horizontal line segment spaced from each other by the unit amount; executing a vertical coordinate value-calculating process for repeatedly carrying out the DDA algorithm-based process whenever the transformed graphic coordinate value-calculating process, the first source graphic coordinate value-calculating process, and the second source graphic coordinate value-calculating process are carried out one time, with a vertical coordinate value of the one of the pair of second points of intersection corresponding to the one of the two sides defining the transformed graphic set to the initial value of the second integer coordinate value used in the DDA algorithm-based process, a vertical coordinate value of the another of the pair of second points of intersection corresponding to the another of the two sides defining the transformed graphic set to the final value of the second integer coordinate value, and the each of integer horizontal coordinate values on the horizontal line segment connecting between the pair of first points of intersection on the two sides defining the transformed graphic set to the first integer coordinate value used in the DDA algorithm-based process, to thereby obtain the second integer coordinate value as a vertical coordinate value of the each of the points on the source graphic corresponding to the respective points on the horizontal line segment spaced from each other by the unit amount; and reading out a portion of the image data of the source graphic from a location within the image memory specified by the horizontal coordinate value obtained by the horizontal coordinate value-calculating process and the vertical coordinate value obtained by the vertical coordinate value-calculating process, for the each of the respective points on the horizontal line segment, and storing the read out portion of the image data in the frame buffer as image data of the transformed graphic corresponding to the each of the respective points on the horizontal line segment.
To attain the above object, according to a third aspect of the invention, there is provided an image processing device comprising an image memory that stores image data of a source graphic before transformation; a frame buffer that stores image data of a transformed graphic after the transformation generated from the source graphic by transforming the source graphic; a first DDA process section that sequentially determines, by a first DDA algorithm-based process, horizontal coordinate values of a pair of first points of intersection where a horizontal scanline intersects with two of sides defining the transformed graphic, while advancing the horizontal scanline in a vertical direction by a unit amount; a second DDA process section that sequentially determines, by a second DDA algorithm-based process, horizontal coordinate values and vertical coordinate values of a pair of second points of intersection on sides of the source graphic corresponding respectively to the two of the sides defining the transformed graphic, the second points of intersection corresponding respectively to the first points of intersection; a third DDA process section that determines, by a third DDA algorithm-based process, a horizontal coordinate value and a vertical coordinate value of each of points on the source graphic corresponding to respective points on a horizontal line segment connecting between one and another of the first points and spaced from each other by the unit amount, the respective points being obtained by changing a horizontal coordinate from a horizontal coordinate value of the one of the first points to a horizontal coordinate value of the another of the first points in the unit amount, whenever the first DDA algorithm-based process and the second DDA algorithm-based process are executed; and a data read/write process section that reads out image data of a location specified by the horizontal coordinate value and the vertical coordinate value of the each of the points on the source graphic determined by the third DDA algorithm-based process, from the image memory, and writes the read out image data into the frame buffer as image data of each of the respective points-on the horizontal line segment connecting between the one and the another of the first points on the transformed graphic and spaced from each other by the unit amount.
To attain the above object, according to a fourth aspect of the invention, there is provided a storage medium storing a program that can be executed by a computer, the program being capable of realizing a image processing method of generating image data of a transformed graphic based on image data of a source graphic before transformation from an image memory, and storing the image data of the transformed graphic into a frame buffer.
The storage medium according to the fourth aspect of the invention is characterized in the the program comprising a module for sequentially determining, by a first DDA algorithm-based process, horizontal coordinate values of a pair of first points of intersection where a horizontal scanline intersects with two of sides defining the transformed graphic, while advancing the horizontal scanline in a vertical direction in unit amounts; a module for sequentially determining, by a second DDA algorithm-based process, horizontal coordinate values and vertical coordinate values of a pair of second points of intersection on sides of the source graphic corresponding respectively to the two of the sides defining the transformed graphic, the second points of intersection corresponding respectively to the first points of intersection;
a module for determining, by a third DDA algorithm-based process, a horizontal coordinate value and a vertical coordinate value of each of points on the source graphic corresponding to respective points on a horizontal line segment connecting between one and another of the first points and spaced from each other by the unit amount, the respective points being obtained by changing a horizontal coordinate from a horizontal coordinate value of the one of the first points to a horizontal coordinate value of the another of the first points in the unit amount, whenever the first DDA algorithm-based process and the second DDA algorithm-based process are executed; and a module for reading out image data of a location specified by the horizontal coordinate value and the vertical coordinate value of the each of the points on the source graphic determined by the third DDA algorithm-based process, from the image memory, and writing the read out image data into the frame buffer as image data of each of the respective points on the horizontal line segment connecting between the one and the another of the first points on the transformed graphic and spaced from each other by the unit amount.